/*
Permutations 

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

*/

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
//#include <math>
#include <stack>
#include <queue>
#include <fstream>
#include <sstream>
#include <unordered_set>
#include <unordered_map>
#include "print.h"
using namespace std;

/**
* Definition for binary tree*/
typedef __int32 uint32_t;


void testForStack()
{
	stack<int> mystack;
	mystack.push(10);
	mystack.push(20);
	mystack.top() -= 5;
	cout << "mystack.top() is now " << mystack.top() << endl;
}

void testForIntToString()
{
	int a = 10;
	stringstream ss;
	ss << a;
	string str = ss.str();
	cout << str << endl;

	string str1 = to_string(a);

}
/*

alpMap[1] = "A";
alpMap[2] = "B";
alpMap[3] = "C";
alpMap[4] = "D";
alpMap[5] = "E";
alpMap[6] = "F";
alpMap[7] = "G";
alpMap[8] = "H";
alpMap[9] = "I";
alpMap[10] = "J";
alpMap[11] = "K";
alpMap[12] = "L";
alpMap[13] = "M";
alpMap[14] = "N";
alpMap[15] = "O";
alpMap[16] = "P";
alpMap[17] = "Q";
alpMap[18] = "R";
alpMap[19] = "S";
alpMap[20] = "T";
alpMap[21] = "U";
alpMap[22] = "V";
alpMap[23] = "W";
alpMap[24] = "X";
alpMap[25] = "Y";
alpMap[26] = "Z";
*/

class Solution {
public:
	bool myNextPermuattion(vector<int> &nums)
	{
		vector<int>::iterator itBegin = nums.begin();
		vector<int>::iterator itEnd = nums.end();

		if (itBegin == itEnd)
		{
			return false;
		}
		
		vector<int>::iterator i = itBegin;
		++i;
		if (i == itEnd)
		{
			return false;
		}

		i = itEnd;
		--i;

		for (;;)
		{
			vector<int>::iterator ii;
			ii = i;
			--i;

			if (*i<*ii)
			{
				vector<int>::iterator j = itEnd;
				while (!(*i < *--j));
				iter_swap(i, j);
				reverse(ii, itEnd);
				return true;
			
			}


			if (i == itBegin)
			{
				reverse(itBegin,itEnd);
				return false;
			}

		}

	}

    vector<vector<int> > permute(vector<int> &num) {
		vector<vector<int> > result;

		if (num.size() == 0)
		{
			return result;
		}

		sort(num.begin(),num.end());

		vector<int> temp;

		result.push_back(num);
		while (myNextPermuattion(num))
		{
			result.push_back(num);

		}

		return result;
    }
};

class Solution1 {
public:
	vector<vector<int> > permute(vector<int> &num) {
		vector<vector<int> > result;

		if (num.size() == 0)
		{
			return result;
		}

		sort(num.begin(), num.end());

		vector<int> temp;

		result.push_back(num);
		while (next_permutation(num.begin(), num.end()))
		{
			result.push_back(num);

		}

		return result;
	}
};




class Solution1 {
public:
	int searchInsert(int A[], int n, int target) {

		int low = 0, high = n - 1;
		while (low <= high)
		{
			int mid = (low + high) >> 1;
			if (A[mid] == target)
			{
				return mid;
			}
			else if (A[mid]>target)
			{
				high = mid - 1;
			}
			else
			{
				low = mid + 1;
			}
		}
		if (high <0)
		{
			return 0;
		}
		if (low >= n)
		{
			return n;
		}
		return low;
	}
};






void func()
{
	auto_ptr<string> ps(new string("jjhou"));

	cout << *ps << endl;
	cout << ps->size() << endl;
}

int main(int argc, char* argv[])
{
	//func();

	
	int a;
	
	//string zeros = "0";
	//int b = zeros[0] - '0';

	vector<int> vecInt;
	
	for (int i = 1; i < argc - 1; i++){


		cout << argv[i] << endl;

		a = atoi(argv[i]);
		vecInt.push_back(a);




		//ListNode *item = new ListNode(a);
		//p->next = item;
		//p = p->next;
		//vecInt.push_back(a);

	}

	//int dividend = 10, divisor = 1;
	//string str1(argv[1]), str2(argv[2]);
	//string result;
	
	Solution s;
	//int target = atoi(argv[argc - 1]);
	vector<vector<int> > result;

	result = s.permute(vecInt);
	

	//cout << result<< endl;

	//head = s.swapPairs(head);
	//string str2 = "23";
	//	char a = str2[2];
	//char one = '1';
	//int num = str2[1] - '0';

	//string str3 = str2 + str2[1];
	//cout << num << endl;

	//Solution s;
	//vector<string> vecStr;
	//vecStr = s.generateParenthesis(a);

	//stackTree.push(p->left);
	//stackTree.push(p->right);

	//ListNode *headA = new ListNode(1);
	//ListNode *pa1 = new ListNode(2);
	//ListNode *pa2 = new ListNode(3);
	//headA->next = pa1;
	//pa1->next = pa2;

	//ListNode *headB = new ListNode(4);
	//ListNode *pa1 = new ListNode(2);
	//ListNode *pa2 = new ListNode(3);
	//headA->next = pa1;
	//pa1->next = pa2;







	system("pause");
	return 0;
}